//package 题目集.线段树or树状数组.树状数组;
//
//import java.util.Arrays;
//import java.util.Scanner;
//
//import org.junit.Test;
//
///**
// * https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
// * 寻找每个数左侧nums[i]比它小的最大长度的个数之和
// * 我们可以维护每个位置
// */
//public class demo03_最长上升子序列的个数 {
//
//	int[] tree;
//	int[] cnts;
//
//	public int findNumberOfLIS(int[] nums) {
//		agge(nums);
//		tree = new int[nums.length + 1];
//		cnts=new int[nums.length+1];
//		int max = 0;
//		for (int v : nums) {
//			int cur = query(v - 1) + 1;
//			cnts[cur]+=cnts[cur-1];
//			ceil(v, cur);
//			max = Math.max(max, cur);
//		}
//		return cnts[max];
//	}
//
//	public void ceil(int x, int v) {
//		for (int i = x; i < tree.length; i += lowbit(i)) {
//			tree[i] = Math.max(tree[i], v);
//		}
//	}
//	public int query(int x) {
//		int ans=0;
//		for(int i=x;i>0;i-=lowbit(i)) {
//			ans=Math.max(ans, tree[i]);
//		}
//		return ans;
//	}
//	
//	public static int lowbit(int x) {
//		return x&-x;
//	}
//
//	public static void agge(int[] arr) {
//		int[] sort = arr.clone();
//		Arrays.sort(sort);
//		for (int i = 0; i < arr.length; i++) {
//			arr[i] = rank(sort, arr[i]);
//		}
//	}
//
//	public static int rank(int[] sort, int v) {
//		int l = 0, r = sort.length - 1;
//		while (l <= r) {
//			int m = l + r >> 1;
//			if (sort[m] < v) {
//				l = m + 1;
//			} else {
//				r = m - 1;
//			}
//		}
//		return l + 1;
//	}
//	
//	@Test
//	public void test() {
//		int[] arr= {1,3,5,4,7};
//		int res=findNumberOfLIS(arr);
//		System.out.println(res);
//	}
//}
